#ifndef _AVL_H_
#define _AVL_H_


#include <stdio.h>
#include <stdlib.h>
#include <string.h>



// 父子节点
#define PARENT_NODE	1
#define CHILD_NODE	0

// 左右孩子
#define LEFT_NODE	1
#define RIGHT_NODE	0


// 树节点
typedef struct avl_node
{
	/*! 数据 */
	int val;

	/*! 此节点的左右节点 */
	struct avl_node* left;
	struct avl_node* right;

	/*! 此节的父节 */
	struct avl_node* parent;
	
	/*! 此节点是父节点的左节点还是右节点 */
	//int flag_left_or_right;

	/*!< 节点的高度 */
	int height;

} avl_node_t;


// 树
typedef struct _t
{
	/*! 树根 */
	struct avl_node* root;

	/*! 树中的节点数 */
	int node_count;
} avl_t;





avl_t* creat_avl();

int destroy_avl();

int is_leaf_node(avl_node_t* node);

avl_node_t* creat_node(int key);

avl_node_t* search_node(avl_node_t* root, int key);

avl_t* insert_node(avl_t* tree, int key);

int calc_tree_height(avl_node_t* root);

int maxDepth(avl_node_t* root);

void updata_node_height(avl_node_t* node);

int rebalance_node(avl_t* tree, avl_node_t* grandpa);

int after_add_node(avl_t* tree, avl_node_t* node);

int after_delete_node(avl_t* tree, avl_node_t* node);

avl_node_t* get_rsb_min_node(avl_node_t* root, avl_node_t** parentNode);

int delete_node(avl_t* tree, int key);

int is_left_child(avl_node_t* node);

int is_right_child(avl_node_t* node);

int delete_leaf_node(avl_t* tree, avl_node_t* del, int flag);

int is_balance(avl_node_t* node);

int rotate_left(avl_t* tree, avl_node_t* grandpa);

int rotate_right(avl_t* tree, avl_node_t* grandpa);

int get_max_val(int a, int b);


void infix(avl_node_t* root);
int level(avl_node_t* root);




#endif // _AVL_H_
